The pioneering work on chaos synchronization [1] led to several applications in communications, in which chaotic systems with continuous-value signals were used to transmit information. Several schemes have been developed which allow transformation of the information signal into a chaotic waveform on the transmitter side and to extract the information signal from the transmitted waveform on the receiver side. The most important among them are chaotic masking, chaos shift keying and chaotic modulation. In early days (from 1992 to 1996) the main research goal was to develop schemes in which a single chaotic system is used for both modulation and encryption. This approach eventually evolved into two distinct research areas: chaos-based modulation [2, 3] and chaos-based cryptography [4, 5].
In chaotic modulation, the digital information is mapped to inherently wide-band chaotic signals. Thus, chaotic modulation offers a novel approach to spread-spectrum communication. Two most promising approaches in chaos-based modulation have recently emerged. In the first approach, the unmodulated chaotic waveform is transmitted along with the modulated signal (transmitted reference scheme) either using a separate channel or using time division. One instance of this approach, called frequency-modulated differential chaos shift keying, was studied in-depth by Kolumban and Kennedy [2, 6]. In another approach, a chaotic reference is regenerated at the receiver with the help of synchronization. In the references [3, 7] an example of such an approach is proposed, in which chaotic time pulsed sequences are used instead of continuous time waveform. Since the information about the state of the chaotic signal is contained entirely in the timing between pulses, the distortions that affect the pulse shape will not significantly influence the ability of the chaotic pulse generators to synchronize. This approach is known as chaotic pulse position modulation.
Cryptography is generally acknowledged as the best method of data protection against passive and active fraud [8]. An overview of recent developments in the design of conventional encryption algorithms is given in [8]. Three most common encryption objects are block-encryption algorithms (private-key algorithms), pseudo-random number generators (additive stream ciphers) and public-key algorithms.
Block ciphers transform a relatively short string (typically 64, 128 or 256 bits) to a string of the same length under control of a secret key. Several block encryption ciphers based on chaotic maps have been proposed, in which a discretization (process that describes the way a chaotic map is implemented in the computer) is not realized by rounding the chaotic map according to the computer arithmetic, but rather is constructed explicitly. Pichler and Scharinger [9] proposed cryptographic systems based on chaotic permutations constructed by explicitly discretizing the two dimensional bakers map. Ridrich [10] extended their ideas to chaotic permutations on any size of two dimensional lattices. The permutations benefit from the expanding property along one axis, technically avoiding the contracting property along the other axis. Masuda and Aihara [11] considered a discrete version of the skew-tent map, which exploits important chaotic properties such as the sensitive dependence on initial conditions and the exponential information decay. They discussed the difference between the discretized map and the original map, explaining the ergodic-like and chaotic-like properties of the discretized map.
A pseudo-random number generator is a deterministic method, usually described with a mapping, to produce from a small set of random numbers, called the seed, and a larger set of random-looking numbers called pseudo-random numbers. Chaotic systems may be used to generate pseudo-random numbers. For example, in a series of papers [12], the authors proposed a chaos derived pseudo-random number generator. They numerically observed that the average cycle and transient lengths grow exponentially with the precision of implementation, and from this fact deduced that using high-precision arithmetic one can obtain PRNGs which are still of cryptographic interest. Statistical properties of binary sequences generated by class of ergodic maps with some symmetrical properties are discussed in [13]. The authors derived a sufficient condition for this class of maps to produce a sequence if independent and identically distributed binary random variables. However, the authors did not discuss the implementation of these maps on finite-state machines and the consequence this implementation may have on the randomness of the generated sequences.
Certain applications in cryptography require the use of a truly random number generator (RNG), which is a device that outputs a sequence of statistically independent and unbiased numbers. It is widely accepted that the core of any RNG must be an intrinsically random physical process. Thus, it is no surprise that the proposals and implementations of RNGs range from tossing a coin, to measuring thermal noise from a resistor and shot noise from a Zener diode or a vacuum tube, measuring radioactive decay from a radioactive source, and sampling a stable high-frequency oscillator with an unstable low-frequency clock, to mention only a few proposals. For chaos-based generators of truly random numbers see for example references [14, 15].
Several applications [16, 17, 18] of chaos in cryptography have been proposed. The work presented in [16, 17, 18] ushers in the era of scientific chaos-based cryptography, which will trigger more research and real-world applications of chaos-based data protection.
In the work [16] a method for generating truly random numbers has been designed and implemented in CMOS technology. Random numbers are crucial importance in every encryption and data protection application. Block encryption algorithm based on chaotic maps are proposed in the patent application “Chaos-based data protection using time-discrete dynamical systems” by L. Kocarev, G. Jakimoski, G. G. Rizzotto, and P. Amato [17]. Lower bounds of number of active S-boxes as well as the upper bounds for differential and linear probabilities in the proposed algorithm have been derived analytically, and therefore, the resistance of this algorithm to differential and linear attacks has been proved. L. Kocarev, P. Amato, and G. G. Rizzotto in [18] have presented a class of pseudo-random-bit generators, for which security does not rely on a number-theoretical problem, and therefore, does not use modular multiplications. In contrast, its security relies on the large numbers of branches for an inverse of a function used in the algorithm. The generators use only binary operations and have been efficiently implemented in software.
The article Communication Theory of Secrecy Systems [22] by C. E. Shannon, published in 1949, ushered in the era of scientific secret-key cryptography. However, Shannon's article did not lead to an explosion of researches on cryptography comparable to that triggered by his earlier articles published in 1948 in information theory [23]. The real explosion of works on cryptography came with an article by W. Diffie and M. E. Hellman [24]. Diffie and Hellman showed for the first time that a secret communication was possible without any transfer of a secret key between sender and recipient, thus starting the era of public-key cryptography. Moreover, they suggested that computational complexity theory could be used for future research in cryptography.
Substantially, an encryption process is a process for transmitting data in a mode that ensures that the data remain private, by converting a message, referred to as a plain-text, into an encrypted format, referred to as a cipher-text. A sender encrypts the message by using an encryption key, while the recipient of the message recovers the plain-text from the received cipher-text by using a decryption key.
Public-key encryption algorithms, also called asymmetric algorithms, are designed so that (i) the encryption key is different from the decryption key; (ii) the encryption key can be made public; and (iii) the decryption key cannot, at least in a reasonable amount of time, be calculated from the encryption key.
There are many public-key algorithms. Only a few of them are both secure and practical, and only three of them work well for both encryption and digital signature: RSA, ElGamal, and Rabin [8]. In a public-key encryption system [8] each entity A has a public key “e” and a corresponding private key “d”. In secure systems, the task of calculating the private key “d” from the public key “e” is practically impossible.
The public key defines an encryption transformation Ee, while the private key defines the associated decryption transformation Dd. A sender B wishing to send a message M to a recipient A must obtain an authentic copy of the recipient public key “e”, use the encryption transformation to obtain the cypher-text c=Ee(M), and transmit the encrypted message “c” to the recipient A. The recipient A decrypts the cipher-text “c” using the decryption transformation and obtains the plain-text M=Dd(C).
Since 1976, numerous public-key algorithms have been proposed. Three most widely used public-key encryption processes are RSA, Rabin and ElGamal. The security of the RSA process is based on the intractability of the integer factorization problem. In the Rabin public-key encryption process, the problem faced by a passive adversary is computationally equivalent to factorizing a number. The security of the ElGamal public-key encryption process is based on the intractability of the discrete-logarithm problem.
Recall first the basic ElGamal algorithm. The ElGamal public-key algorithm can be viewed as Diffie-Hellman key agreement in key transfer-mode [8]. Consider a class of functions defined as πp(x)=xp(mod N) wherein N is a prime number, and x is a generator of the multiplicative group Z*N, and 1≦p≦N−2.
Any two functions πp and πq, commute under composition:πp(πq(x)=πpq(x)
The Diffie-Hellman key agreement protocol describes how Alice and Bob agree on their common secret key. Alice generates a number p, computes y=πp(x) and sends (x, y) to Bob. Bob creates a number q, computes z=πq(x) and sends z to Alice. The secret key, which can be shared by both Alice and Bob, is computed as follows. Alice computes the secret key k as k=πp(z), Bob computes the secret key k as k=πq(y).
In the ElGamal public-key scheme, Alice generates a large random prime N and a generator x of the multiplicative group Z*N of integers modulo N. She also generates a random integer s≦N−2 and computes A=xs(mod N). Alice's public key is (x, N, A); Alice's private key is s. To encrypt a message m, Bob selects a random integer r≦N−2, computes B=xr(mod N) and X=mAr(mod N), and sends the cipher-text c=(B,X) to Alice. To recover the message m from c, Alice uses the private key s to recover m by computing m=B−sX(mod N). The decryption allows recovery of the original message because B−smAr≡x−rsmxrs≡m(mod N).
Recall now the RSA algorithm. Let N=pq and φ=(p−1)·(q−1), where p and q are two large random (and distinct) primes p and q. Alice selects a random integer e, 1<e<φ, such that the greatest common divisor of “e” and “φ” is 1:gcd(e,φ)=1and computes the unique integer d, 1<d<φ, such that ed≡1(mod φ).
Alice's public key is (N, c); Alice's private key is d. To encrypt a message m, Bob computes c=me(mod N) and sends it to Alice. To recover the message m from c, Alice should use the private key d to recover m=ce(mod N).
Let πp(x)=xp(mod N). The decryption in the RSA algorithm works for two reasons: the functions πe and πd commute under composition, and p is a periodic point of the function πed for every m such that med≡m(mod N). The last follows from the following observation. Since ed≡1(mod φ), there is an integer k such that ed=1+kφ. If gcd(m,p)=1 then by Fermat's theorem mp−1≡1(mod p). Raising both sides of this congruence to the power of k·(q−1) and then multiplying both sides by m yields med≡m(mod p).
By the same argument it is possible to demonstrate that med≡m(mod q). Finally, since p and q are distinct primes, thus med≡m(mod N). Public-key encryption processes are much slower than symmetric-key encryption algorithms. For this reason, public-key encryption is most commonly used for encrypting short data and/or for transporting encryption keys, subsequently used for data encryption by symmetric-key algorithms.